package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;

/**
 * 树节点
 *
 * @author c2b
 * @since 2022/5/20 09:29
 */
public class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static void printTreeNodeValF(List<Integer> ans) {
        for (Integer integer : ans) {
            System.out.print(integer + "  ");
        }
        System.out.println();
    }

    public static void printTreeNodeVal(List<List<Integer>> ans) {
        for (List<Integer> integers : ans) {
            for (Integer integer : integers) {
                System.out.print(integer + "  ");
            }
            System.out.println();
        }
    }

    // 层序遍历

    static int height = 0;
    static int valMaxLength = 1;

    public static void printTree(TreeNode root) {
        List<List<String>> lists = printTreeHelper(root);
        for (List<String> list : lists) {
            for (String s : list) {
                StringBuilder builder = new StringBuilder();
                for (int i = 0; i < valMaxLength - s.length(); i++) {
                    builder.append(" ");
                }
                builder.append(s);
                System.out.print(builder);
            }
            System.out.println();
        }
    }


    private static List<List<String>> printTreeHelper(TreeNode root) {
        getMaxHeight(root, 0);
        int row = height + 1;
        int col = (int) (Math.pow(2, height + 1) - 1);
        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            List<String> tempList = new ArrayList<>();
            for (int j = 0; j < col; j++) {
                tempList.add("");
            }
            res.add(tempList);
        }
        fillVal(root, 0, (col - 1) >> 1, res);
        return res;
    }

    private static void fillVal(TreeNode root, int row, int col, List<List<String>> res) {
        if (root == null) {
            if (row < res.size() && col < res.get(0).size()) {
                res.get(row).set(col, "n");
            }
            return;
        }
        String value = String.valueOf(root.val);
        valMaxLength = Math.max(value.length(), valMaxLength);
        res.get(row).set(col, value);
        fillVal(root.left, row + 1, col - (int) Math.pow(2, height - row - 1), res);
        fillVal(root.right, row + 1, col + (int) Math.pow(2, height - row - 1), res);
    }

    private static void getMaxHeight(TreeNode root, int currLevel) {
        if (root == null) {
            return;
        }
        if (currLevel > height) {
            height = currLevel;
        }
        getMaxHeight(root.left, currLevel + 1);
        getMaxHeight(root.right, currLevel + 1);
    }
}
